//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 
//
// 有效字符串需满足： 
//
// 
// 左括号必须用相同类型的右括号闭合。 
// 左括号必须以正确的顺序闭合。 
// 每个右括号都有一个对应的相同类型的左括号。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "()"
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：s = "()[]{}"
//输出：true
// 
//
// 示例 3： 
//
// 
//输入：s = "(]"
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 10⁴ 
// s 仅由括号 '()[]{}' 组成 
// 
//
// Related Topics 栈 字符串 👍 3847 👎 0


package leetcode.editor.cn;

// [20]有效的括号

import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;

public class ValidParentheses_20 {
    public static void main(String[] args) {
        Solution solution = new ValidParentheses_20().new Solution();
        String s = "([)";
        System.out.println(solution.isValid(s));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean isValid(String s) {
            if (s == null || s.length() < 2) {
                return false;
            }
            HashMap<Character, Character> map = new HashMap<>(8);
            map.put(')', '(');
            map.put(']', '[');
            map.put('}', '{');
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == '(' || c == '[' || c == '{') {
                    stack.push(c);
                    continue;
                } else if (stack.isEmpty()) {
                    return false;
                } else {
                    if (stack.peek().equals(map.get(c))) {
                        stack.pop();
                    } else {
                        return false;
                    }
                }
            }
            return stack.isEmpty();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    class Solution2 {
        public boolean isValid(String s) {
            int n = s.length();
            if (n == 0) return false;
            if ((n & 1) == 1) return false;
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < n; i++) {
                char tmp = s.charAt(i);
                if (stack.isEmpty() && (tmp == ')' || tmp == ']' || tmp == '}')) return false;
                if (tmp == '(' || tmp == '[' || tmp == '{') {
                    stack.push(tmp);
                    continue;
                }
                if (tmp == ')' && stack.pop() != '(') return false;
                if (tmp == ']' && stack.pop() != '[') return false;
                if (tmp == '}' && stack.pop() != '{') return false;
            }
            if (!stack.isEmpty()) return false;
            else return true;
        }
    }

}